package leetcode.solution;

/**
 * @author : zx
 * @version V1.0
 * 给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。
 *
 * 示例:
 *
 * 输入: matrix = [[1,0,1],[0,-2,3]], k = 2
 * 输出: 2
 * 解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
 * 说明：
 *
 * 矩阵内的矩形区域面积必须大于 0。
 * 如果行数远大于列数，你将如何解答呢？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k
 */
public class 最大矩阵和 {
    /**
     * 解法一 动态规划+暴力穷举 无法处理大规模数据
     */
    public static int maxSumSubmatrix(int[][] matrix, int k) {
        int width = matrix.length;
        int height = matrix[0].length;
        // 起始行数、结束行数、起始列数、结束列数
        int[][][][] dp = new int[width][width][height][height];
        // 最大矩阵和 注意不应使用0 因为可能有负数情况
        int max = Integer.MIN_VALUE;
        // 行 w1 起点 w2 终点 列 h1 起点 h2 终点
        for (int w1 = 0; w1 < width; w1++){
            for (int w2 = w1; w2 < width; w2++){
                for (int h1 = 0; h1 < height; h1++){
                    for (int h2 = h1; h2 < height; h2++){
                        if (w1==w2 && h1==h2){
                            // 初始值
                            dp[w1][w2][h1][h2] = matrix[w1][h1];
                        }else if (w1 == w2){
                            // 同行
                            dp[w1][w2][h1][h2] = dp[w1][w2][h1][h2-1] + matrix[w1][h2];
                        }else if (h1 == h2){
                            // 同列
                            dp[w1][w2][h1][h2] = dp[w1][w2-1][h1][h2] + matrix[w2][h1];
                        }else {
                            dp[w1][w2][h1][h2] = dp[w1][w2][h1][h2-1] + dp[w1][w2-1][h1][h2] - dp[w1][w2-1][h1][h2-1] + matrix[w2][h2];
                        }
                        if (dp[w1][w2][h1][h2]<=k && dp[w1][w2][h1][h2]>max){
                            max = dp[w1][w2][h1][h2];
                        }else if (dp[w1][w2][h1][h2] == k){
                            return dp[w1][w2][h1][h2];
                        }
                    }
                }
            }
        }
        return max;
    }

    /**
     * 解法一优化 动态规划+暴力穷举 可以很容易想到实际上遍历是先确定左上角坐标即起点的基础上开始的
     * 那么我们只要假设起点不变，这道题就变成了一道固定起点寻找最大矩阵和的题
     */
    public static int maxSumSubmatrix_2(int[][] matrix, int k) {
        int width = matrix.length;
        int height = matrix[0].length;
        // 结束行数、结束列数
        int[][] dp = new int[width][height];
        // 最大矩阵和 注意不应使用0 因为可能有负数情况
        int max = Integer.MIN_VALUE;

        // 先确定起点
        for (int w1 = 0; w1 < width; w1++){
            for (int h1 = 0; h1 < height; h1++){

                for (int w2 = w1; w2 < width; w2++){
                    for (int h2 = h1; h2 < height; h2++){
                        if (w2==w1 && h2==h1){
                            dp[w1][h1] = matrix[w1][h1];
                        }else if (w1 == w2){
                            dp[w2][h2] = dp[w1][h2-1] + matrix[w2][h2];
                        }else if (h1 == h2){
                            dp[w2][h2] = dp[w2-1][h2] + matrix[w2][h2];
                        }else {
                            dp[w2][h2] = dp[w2-1][h2] + dp[w2][h2-1] - dp[w2-1][h2-1] + matrix[w2][h2];
                        }
                        if (dp[w2][h2]<=k && dp[w2][h2]>max){
                            max = dp[w2][h2];
                        }else if (dp[w2][h2] == k){
                            return dp[w2][h2];
                        }
                    }
                }
            }
        }
        return max;
    }

    /**
     * 优化运行速度
     * 通过循环计算从l到r列每行元素之和，然后取dp的最大连续子数组则为l到r的最大矩阵和
     */
    public int maxSumSubmatrix_3(int[][] matrix, int k) {
        int rows = matrix.length, cols = matrix[0].length, max = Integer.MIN_VALUE;
        // O(cols ^ 2 * rows)
        for (int l = 0; l < cols; l++) { // 枚举左边界
            int[] rowSum = new int[rows]; // 左边界改变才算区域的重新开始
            for (int r = l; r < cols; r++) { // 枚举右边界
                for (int i = 0; i < rows; i++) { // 按每一行累计到 dp
                    rowSum[i] += matrix[i][r];
                }
                max = Math.max(max, dpmax(rowSum, k));
                if (max == k) return k; // 尽量提前
            }
        }
        return max;
    }
    // 在数组 arr 中，求不超过 k 的最大值
    private int dpmax(int[] arr, int k) {
        int rollSum = arr[0], rollMax = rollSum;
        // O(rows)
        for (int i = 1; i < arr.length; i++) {
            if (rollSum > 0) rollSum += arr[i];
            else rollSum = arr[i];
            if (rollSum > rollMax) rollMax = rollSum;
        }
        if (rollMax <= k) return rollMax;
        // O(rows ^ 2)
        int max = Integer.MIN_VALUE;
        for (int l = 0; l < arr.length; l++) {
            int sum = 0;
            for (int r = l; r < arr.length; r++) {
                sum += arr[r];
                if (sum > max && sum <= k) max = sum;
                if (max == k) return k; // 尽量提前
            }
        }
        return max;
    }


    public static void main(String[] args){
        System.out.println();
    }
}
